package main

import (
	"fmt"
	"math/rand"
	"sort"
)

func main() {
	// 第一题
	// s1 := make([]int, 3, 4)
	// s2 := append(s1, 1)
	// fmt.Printf("%p %p %d %d %v\n", &s1, &s1[0], len(s1), cap(s1), s1)
	// fmt.Printf("%p %p %d %d %v\n", &s2, &s2[0], len(s2), cap(s2), s2)
	// (1) s1 [0 0 0]  s2 [0 0 0 1]
	// (2) 修改s2会影响s1 修改s1也会影响s2  因为s1和s2两个数组，指向同一个底层数组
	// (3) s2和s1共用一个底层数组，其cap为4，我们在上面代码基础上在增加一个元素，则len=5，cap=4 len > cap  触发底层数组扩容策略
	// newcap = 2 * oldcap  = 2 * 4 = 8, len = 5 。从此刻开始s2 将不与s1共用底层数组。新的s2 与 s1 分道扬镳，在更新和添加元素上互不影响

	// 第二题
	array := [...]int{1, 4, 9, 16, 2, 5, 10, 15}
	newArray := make([]int, 0, len(array)-1)
	for i := 0; i < len(array)-1; i++ {
		newArray = append(newArray, array[i]+array[i+1])
	}
	fmt.Println(newArray)
	// 题解如上，应该还有更好的解，暂时还没有想出来

	// 第三题
	number := make([]int, 0, 100)
	appearCount := make(map[int]int, 100)
	for i := 1; i <= 100; i++ {
		n := rand.Intn(401) - 200
		number = append(number, n)
		if _, ok := appearCount[n]; ok {
			appearCount[n]++
		} else {
			appearCount[n] = 1
		}

	}
	sort.Ints(number)
	for _, v := range number {
		fmt.Printf("%d %d\n", v, appearCount[v])
	}
	// 第四题
	// 简述线性数据结构和哈希表的优劣
	// 线性数据结构可以分为顺序表、链表、栈、队列
	// 顺序表，在开辟内存地址的时候会开辟一个连续的内存空间，且每个内存空间占有的大小相同，在尾部增加一个元素，效率较高，但是，
	// 在进行非尾部修改和追加的时候，追加后的后面的元素都会往后移动。效率较低，其操作的时间复杂度为O(n)。
	// 连接表，在存储数据是，开辟的内存地址是不连续的，可以分为单向链表和双向链表两种。单向链表只能从前往后找，内个元素只有next指针，双向链表既能从前往后，也能
	// 从后往前找，每个元素有next和prev两个指针，在做非尾部插入和删除操作的时候，效率相对于顺序表高。
	// 顺序表和链接表在遍历上时间复杂度都是O(n),链接表相对于顺序表灵活。
	// 栈：FIFO(后进先出)，只会在一端操作。典型的例子：摆盘子、压子弹。插入和弹出元素的时间复杂度都是O(1)。不能在首部和中间进行操作
	// 队列：FIFO(先进先出)，只会在两端操作。插入和删除元素的时间复杂度都是O(1)。不能在中间进行操作。队列的作用：用来平峰流量，将同步转换为异步。
	// 哈希表，存放的为kv对，有桶数组组成，对每个key都需要进行哈希判断将需要将kv对存放在那个桶里面。哈希表的增删改查的操作的时间复杂度都是O(1)。效率相对较高
	// 存在极端的情况，就是一个桶里面存放的大量的kv对，存放不平衡，此时哈希表退化为链表，查看和删除的操作都为O(n)。我们可以使用增量扩容和等量扩容的方式来对通数组进行
	// 扩容，防止哈希表退化为链表。

}
